package com.example.file;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Stack;

/**
 * @author: dangwen
 * @createDate: 2021/7/7
 */
public class Node {

    private Integer value;
    private Node next;

    public static void main(String[] args) {

        //4-5
        Node node1 = new Node();
        node1.value = 4;
        Node node3 = new Node();
        node3.value = 5;
        node1.next = node3;

        //6-9-5
        Node node2 = new Node();
        node2.value = 6;
        Node node4 = new Node();
        node4.value = 9;
        node2.next = node4;
        Node node6 = new Node();
        node6.value = 5;
        node4.next = node6;

        //结果7-4-0
//        Node node3=add(node1,node2);

        Node resultNode = add(node1,node2);
        while (resultNode != null){
            System.out.println(resultNode.value);
            resultNode = resultNode.next;
        }
    }

    public static Node add(Node node1, Node node2){
        Stack<Integer> node1Stack = node1InputMethod(node1);
        Stack<Integer> node2Stack = node1InputMethod(node2);
        Node resultNode = getSum(node1Stack, node2Stack, 0);
        return sortElement(resultNode);
    }

    public static Stack<Integer> node1InputMethod(Node node){
        Stack<Integer> stack = new Stack<>();
        while (node != null && node.value != null){
            stack.push(node.value);
            node = node.next;
        }
        return stack;
    }

    public static Node getSum(Stack<Integer> stack1, Stack<Integer> stack2, int high){
        Node node = new Node();
        int sum = 0;
        Integer stackNum = 0;
        if(!stack1.isEmpty() && !stack2.isEmpty()){
            Integer stack1Num = stack1.pop();
            Integer stack2Num = stack2.pop();
            sum = stack1Num + stack2Num;
            sum += high;
            high = sum/10;
            node.value = sum%10;
            Node newNode = getSum(stack1, stack2, high);
            node.next = newNode;
        }
        if(stack1.isEmpty() && stack2.isEmpty()){
            return node;
        }else if(stack1.isEmpty()){
            stackNum = stack2.pop();
        }else{
            stackNum = stack1.pop();
        }
        node.value = (high + stackNum + sum) == 10 ? 0 : high + stackNum + sum;
        return node;
    }

    public static Node sortElement(Node node){
        if (node == null || node.next == null){
            return node;
        }
        Node newNode = sortElement(node.next);
        node.next.next = node;
        node.next = null;
        return newNode;
    }

}
